Many laser and inkjet printers currently produced cannot print the many shades of gray or color (typically 256 or more shades) that are necessary to simulate continuous grayscale or multi-color images, also referred to as contone images. These printers typically only print utilizing one color ink, e.g. cyan, magenta, yellow or black ink, and therefore, at a given space on a page, the printer can either leave the space blank or place a dot of ink thereon. By changing the density of dots, or the size of the dots, on areas of the page, an assimilation of contone images can be made. This process of mimicking a contone image through use of varied densities of dots is referred to as halftoning. In halftoning, the image being created is defined into a plurality of small cells. A number of dots are then arranged in a pattern within the cell. The number and the pattern of the dots are dependent upon the particular shade of gray or color that is to be simulated and upon the type of halftoning that is being utilized.
There are two classes into which halftoning techniques for printing applications can be divided. The first is referred to as “classical halftoning” in which the classical screen is simulated and the contone image is replaced by dots of variable size located on a fixed rotated rectangular grid. Here, each dot is created using groups of tiny laser spots. A second is referred to as “stochastic halftoning” in which the contone image is replaced by equally sized dots at varying places. The dots appear to be distributed in a stochastic or random fashion.
In photographically generated halftones, a photo sensitive media receives the image through a halftone screen, creating smaller dots for lighter areas and larger dots for darker areas. These images are considered analog images. Digitally composed printing prints only one size of dot, but varies the density of dots in an area, by clustering them together.
Originally, a halftoning procedure was performed by means of a screen, e.g. “screening.” With today's increase in the power of computers, halftoning is more and more frequently performed in a digital fashion by raster image processors (RIPs). The halftoning operation is a computationally intensive application, and the resulting image sizes are large, since in forming the image a pattern of dots representing a shade of gray must be mapped rather than, for example, just a reference to the particular shade of gray that is required in a portion of a grayscale image.
In order to simulate variable-sized halftone dots in computer printers, dithering is used, which creates clusters of dots in a halftone cell. The more dots printed in the cell, the darker the shade of gray that is depicted. As the screen frequency gets higher (i.e. more cells per inch), there is less room for dots in the cell, reducing the number of shades of gray or color that can be generated.
In low resolution printers, there is always a compromise between printer resolution (dpi) and screen frequency (lpi), which is the number of rows of halftone cells per inch. For example, in a 300 dpi printer, the 8×8 halftone cell required to create 64 shades of gray results in a very coarse 38 lines per inch of screen frequency (300 dpi divided by 8). However, a high resolution, 2400 dpi imagesetter can easily handle 256 shades of gray at 150 lpi (2400/16). At this resolution, the human viewer cannot distinguish black and white dots from continuous gray.
Halftone images, also called bi-level images, tend to be very large. That is, the image can range from a few megabits (Mbit) up to several gigabits (Gbit). When images are screened at a high resolution, the size of the halftone image can be several times larger than the size of the original contone image. Hence, storage and transmission of these images can benefit from compression.
However, halftones are not typically compressible, and the methods that have been developed to date often resort to a loss of image information during the compression process called “lossy compression”. Previous methods to compress halftone images may convolve the images with low-pass filters to convert them back to contone images which are then compressed with such well-known techniques such as JPEG, but this technique is a lossy compression method and therefore results in a loss of information image information.
High-resolution digital printers and growing computational requirements associated with new applications, such as printing-on-demand and personalized printing have increased the need for fast and efficient lossless halftone image compression.